package test230606;

/**
 * @author 兴趣使然黄小黄
 * @version 1.0
 * @date 2023/6/6 20:11
 * 92. 反转链表 II
 * https://leetcode.cn/problems/reverse-linked-list-ii/
 */
public class Solution01 {

    public ListNode reverseBetween(ListNode head, int left, int right) {
        // 使用虚拟头节点作为辅助节点
        ListNode headNode = new ListNode();
        headNode.next = head;  // 最终需要返回的头指针为 headNode.next
        // 头插法的思想反转链表
        ListNode pre = headNode;
        ListNode cur = head;
        int n = right - left + 1;  // 计算需要反转的节点数量
        // 先找到 left 位置
        while (--left != 0) {
            pre = pre.next;
            cur = cur.next;
        }
        // 依次头插反转 n 个节点
        pre.next = null;
        ListNode temp = cur;
        while (n-- != 0) {
            ListNode curNext = cur.next;
            cur.next = pre.next;
            pre.next = cur;
            cur = curNext;
        }
        temp.next = cur;
        return headNode.next;
    }

    private class ListNode {
        int val;
        ListNode next;
        ListNode() {}
        ListNode(int val) { this.val = val; }
        ListNode(int val, ListNode next) { this.val = val; this.next = next; }
    }
}
